#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    // int triangleNumber(vector<int>& nums) {
    //     int n = nums.size();
    //     sort(nums.begin(), nums.end());

    //     int ret = 0;
    //     for (int i = 0; i < n; i++)
    //     {   
    //         for (int j = i + 1; j < n; j++)
    //         {
    //             int left = j + 1, right = n - 1;
    //             int k = j;
    //             while (left <= right)
    //             {
    //                 int mid = (right - left) / 2 + left;
    //                 if (nums[i] + nums[j] > nums[mid])
    //                 {
    //                     k = mid;
    //                     left = mid + 1;
    //                 }
    //                 else
    //                     right = mid - 1;
    //             }

    //             ret += k - j;
    //         }
    //     }

    //     return ret;
    // }

    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        int ret = 0;
        for (int i = n - 1; i >= 2; --i)
        {
            int left = 0, right = i - 1;
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    while (left < right && nums[left] == nums[++left]);
                }
            }
        }

        return ret;
    }
};
